class Node():
    def __init__(self,value):
        self.value=value
        self.next=None

#建立链表
node1=Node(1)
node2=Node(4)
node3=Node(3)
# node4=Node(6)
# node5=Node(7)
node1.next=node2
node2.next=node3
# node3.next=node4
# node4.next=node5


#写链表打印函数
def printlink(head):
    while head!=None:
        print(head.value,'-> ',end="")
        head=head.next
    print("null")
printlink(node1)



class Solution:
    def reorderList(self , head ):
        # write code here
        #找到中间节点，利用快慢指针，当快指针是慢指针的两杯，当快指针到底的时候，满指针就是中间节点
        fast=head
        slow=head
        while fast.next!=None:
            fast=fast.next
            fast=fast.next
            slow=slow.next
        printlink(slow)
        #后节点反转
        r=None
        while slow.next!=None:
            tmp=slow.next
            slow.next=r
            r=slow
            slow=tmp
        slow.next=r
        mhead=slow
        printlink(mhead)

        # 拼接链表,head,mhead
        result=Node(-1)
        t=result
        while mhead!=None:
            tmp1=mhead.next
            tmp2=head.next
            result.next=head
            result.next.next=mhead
            result=result.next.next
            mhead=tmp1
            head=tmp2
        if mhead:
            result.next=head
            result.next.next=mhead
            result=result.next.next
        result.next=None
        return t.next
so=Solution()
result=so.reorderList(node1)
printlink(result)
